Masala #R108D

Qishning sovuq va zerikarli kunlarida Shohruh o'ziga yangi quvonch izlab kazinoga yo'l oldi. U yerda "Aqllilar o'yini" deb nomlangan ajabtovur o'yinga ko'zi tushdi.

O'yin qoidalari quyidagicha:

• Kazinoning sirli generatori ketma-ket \(K\) marta, har gal \(N\) xil sovg'alardan tasodifiy birini taklif qiladi.
• Har bir raundda, Shohruhga bir sovg'a chiqariladi va u bevosita qaror qabul qilishi kerak: oladimi yoki rad etadimi?
• Agar Shohruh sovg'ani rad etsa, u sovg'a g‘oyib bo’ladi va keyingi bosqichga o‘tiladi (ortga qayta olib bo‘lmaydi!).

Har bir sovg'a turi bir xil ehtimollikda chiqadi va raundlar bir-biriga bog‘liq emas.
Hatto ketma-ket bir necha bor bir xil sovg'a chiqishi ham mumkin.
Yuqoridagi o'yinda, Shohruh \(P_i\) ball olib keladigan \(i\)-tur sovg‘ani olishni xohlashi mumkin. Biroq, har bir \(i\)-tur sovg'aning "majburiy to'plami" – ya’ni olishdan oldin to'plashi shart bo'lgan sovg'alar ro‘yxati \(S_i\) bor.

Shohruh faqat \(S_i\) to‘plamidagi barcha sovg’alarni oldin olganidan keyin \(i\)-tur sovg‘ani olishi mumkin.

(Agar hali ololmaydigan sovg'a chiqsa va u o'sha paytda rad qilinadigan holatda bo‘lsa, bu imkoniyat havoga uchdi deganidir!)

Optimal strategiyaga rioya qilgan holda, Shohruh ushbu o'yindan olish mumkin bo'lgan o'rtacha balining qiymati qancha bo‘ladi?

Birinchi qatorda \(K\) (tur soni) va \(N\) (sovg'alar soni) beriladi.

So'ng, har bir sovg'a uchun quyidagilar beriladi:

• Birinchi qatorda \(P_i\) (sovg’a bergan ballar) va \(|S_i|\) (ushbu sovg‘aga yetish uchun dastlab bajarilishi kerak bo‘lgan sovg’alar soni).
• Keyingi qatorda, agar mavjud bo‘lsa, talablarga mos ravishda kerakli sovg’alar raqamlari ro‘yxati keltiriladi.

Cheklovlar:

• \(1 \le K \le 100\)
• \(1 \le N \le 15\)
• \(-10^9 \le P_i \le 10^9\)

O'yin yakunida olish mumkin bo'lgan o'rtacha ball qiymatini \(10^{-5}\) aniqlikgacha ekranga chiqaring.